/*
 * @lc app=leetcode.cn id=673 lang=javascript
 *
 * [673] 最长递增子序列的个数
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var findNumberOfLIS = function (nums) {
  // 以 nums[i] 结尾的最长严格递增子序列的长度
  const length = new Array(nums.length).fill(1);
  // 以 nums[i] 结尾的最长递增子序列的个数
  const count = new Array(nums.length).fill(1);
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        if (length[j] + 1 > length[i]) {
          length[i] = length[j] + 1;
          count[i] = count[j];
          // 又找到一个与当前最大值等长的以 num[j] 结尾的子序列
        } else if (length[j] + 1 === length[i]) {
          count[i] += count[j];
        }
      }
    }
  }

  const maxLen = Math.max(...length);
  // 计算最长递增子序列的个数
  const res = length.reduce(
    (acc, cur, idx) => (acc += cur === maxLen ? count[idx] : 0),
    0
  );
  return res;
};
// @lc code=end
